package com.yubest;

/**
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * <p>
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,0]
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 示例 3：
 * <p>
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 5 * 10^5
 * -2^31 <= nums[i] <= 2^31 - 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/first-missing-positive
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/22 14:48
 */
public class P0041 {

    public static void main(String[] args) {
        System.out.println(new Solution41().firstMissingPositive(new int[]{1, 2, 0}));

        System.out.println(new Solution41().firstMissingPositive(new int[]{3, 4, -1, 1}));

        System.out.println(new Solution41().firstMissingPositive(new int[]{7, 8, 9, 11, 12}));

        System.out.println(new Solution41().firstMissingPositive(new int[]{1}));

        System.out.println(new Solution41().firstMissingPositive(new int[]{-5}));

        System.out.println(new Solution41().firstMissingPositive(new int[]{1, 1}));

        System.out.println(new Solution41().firstMissingPositive(new int[]{3, 4, -1, 1}));
    }
}

class Solution41 {

    /**
     * 思路：假设数组长度为n，则没有出现的最小的正整数一定在[1, n + 1]之间
     *
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //将所有小于等于0的数赋值为 n + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            //如果某个数存在，则将对应的下标里的数赋值为负值
            if (Math.abs(nums[i]) >= 1 && Math.abs(nums[i]) <= n) {
                nums[Math.abs(nums[i]) - 1] = - Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        int index = -1;
        for (int i = 0; i < n; i++) {
            //如果某个数为正数，则说明此数在原数组中未出现过
            if (nums[i] > 0) {
                index = i;
                break;
            }
        }
        return index >= 0 ? index + 1 : n + 1;
    }
}
